#ifndef __LINKLIST_H_
#define __LINKLIST_H_

#include <iostream>

template<typename T>
class LinkList
{
public:
    LinkList()
    {
        head = new Node();
        head->next = nullptr;
        head->element = T();
        size = 0;
    }
    ~LinkList()
    {
        while(head != nullptr)
        {
            Node *temp = head->next;
            delete head;
            head = temp;
        }
        size = 0;
    }
    int Size(){return size;}
    void InsertTail(const T& element);
    void InsertHead(const T& element);
    void RemoveByIndex(int index);
    T& FindByIndex(int index);
    
    template<typename U>
    friend std::ostream& operator<<(std::ostream& os,const LinkList<U>& list);

private:
    struct Node
    {
        Node(){}
        Node(const T& element):element(element),next(nullptr){}
        T element;//数据域
        Node *next;//指针域
    };
    Node *head;
    int size;
};

template <typename T>
void LinkList<T>::InsertTail(const T &element)
{
    Node* TravelPoint = this->head;
    while(TravelPoint->next != nullptr)
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->next = new Node(element);
    size++;
}

template <typename T>
void LinkList<T>::InsertHead(const T &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

template <typename T>
void LinkList<T>::RemoveByIndex(int index)
{
    Node* TravelPoint = head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    Node *FreeNode = TravelPoint->next;
    TravelPoint->next = FreeNode->next;
    delete FreeNode;
    size--;
}

template <typename T>
inline T &LinkList<T>::FindByIndex(int index)
{
    Node* TravelPoint = head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return TravelPoint->element;
}

template<typename U>
std::ostream& operator<<(std::ostream& os,const LinkList<U>& list)
{
    //声明后面跟着的是类型 否则会被认为是函数
    typename LinkList<U>::Node* TravelPoint = list.head->next;
    while(TravelPoint != nullptr)
    {
        os<<TravelPoint->element<<" ";
        TravelPoint = TravelPoint->next;
    }
    return os;
}




#endif